// RMQ《int, N> rq(A)
// vector<int> A(n + 1)
template <class Ty, const i64 logn>
struct RMQ {
    using i64 = long long;
    std::vector<std::array<Ty, logn>> info1;
    std::vector<std::array<Ty, logn>> info2;
  
    RMQ(const std::vector<Ty>& A) { 
        init(A); 
    }
    void init(const std::vector<Ty>& A) {
        i64 n = A.size() - 1;
        info1.assign(A.size(), std::array<Ty, logn>{});
        info2.assign(A.size(), std::array<Ty, logn>{});
        for (int i = 1; i <= n; ++i) {
            info1[i][0] = A[i];
            info2[i][0] = A[i];
        }
        for (int j = 1; j <= logn; ++j) {
            for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
                info1[i][j] = merge1(info1[i][j - 1], info1[i + (1 << j - 1)][j - 1]);
                info2[i][j] = merge2(info2[i][j - 1], info2[i + (1 << j - 1)][j - 1]);
            }
        }
    }

    Ty QueryMax(i64 l, i64 r) {
        if (l > r) {
            std::swap(l, r);
        }
        i64 j = std::__lg(r - l + 1);
        return merge1(info1[l][j], info1[r - (1 << j) + 1][j]);
    };

    Ty QueryMin(i64 l, i64 r) {
        if (l > r) {
            std::swap(l, r);
        }
        i64 j = std::__lg(r - l + 1);
        return merge2(info2[l][j], info2[r - (1 << j) + 1][j]);
    }

    constexpr Ty merge1(const Ty& a, const Ty& b) {
        return std::max(a, b);
    }
    
    constexpr Ty merge2(const Ty& a, const Ty& b) {
        return std::min(a, b);
    }
};
 
const int N = std::__lg(100000) + 1;